package leetcode_700;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *SmallestRange_632 给定N个已排序数组 要求求出一个最小区间 这个区间涵盖n个数组里 n个元素 
 *describe: 滑动窗口问题 用优先队列解决  AC 50%
 *2018年9月24日 上午9:53:21
 */
public class SmallestRange_632 {
	
	
	
	/**
	 * describe:优先队列实现
	 * 2018年9月24日 上午9:52:19
	 */
	public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Node> minQueue = new PriorityQueue<>(10, new Comparator<Node>() {  
            @Override
            public int compare(Node w1, Node w2) {                         
                return w1.val - w2.val;  
            }      
        });
        int big = 0;
        for (int i = 0; i < nums.size(); i++) {
            minQueue.offer(new Node(i, 0, nums.get(i).get(0)));
            big = Math.max(big, nums.get(i).get(0));
        }
        int gsmall = 0;
        int gbig = Integer.MAX_VALUE;
        while(!minQueue.isEmpty()) {
            Node n = minQueue.poll();
            int small = n.val;
            int index = n.index;
            int sindex = n.sindex;
            if (Math.abs(big-small) < Math.abs(gbig-gsmall) || (Math.abs(big-small) == Math.abs(gbig-gsmall) && big < gbig)) {
                gsmall = small;
                gbig = big;
            }
            if (sindex + 1 >= nums.get(index).size()) {
                break;
            }
            int num = nums.get(index).get(sindex+1);
            big = Math.max(big, num);
            minQueue.offer(new Node(index, sindex+1, num));
        }
        int[] res = new int[2];
        res[0] = gsmall;
        res[1] = gbig;
        return res;
    }
    
    class Node {
        int index;
        int sindex;
        int val;
        public Node(int index, int sindex, int val) {
            this.index = index;
            this.sindex = sindex;
            this.val = val;
        }
    }
	/**
	 * describe:N指针遍历 在最后一个用例超时 
	 * 2018年9月24日 上午9:49:26
	 */
	public int[] smallestRange1(List<List<Integer>> nums) {
        int minIndex=0,maxIndex=0;
        for(int i=1;i<nums.size();++i) {
        	if(nums.get(i).get(0)<nums.get(minIndex).get(0))
        		minIndex=i;
        	if(nums.get(i).get(0)>nums.get(maxIndex).get(0))
        		maxIndex=i;
        	//初始化遍历第一个元素
        }
        int res=nums.get(maxIndex).get(0)-nums.get(minIndex).get(0);
        if(nums.get(minIndex).size()==1)
        	return new int[] {nums.get(minIndex).get(0),nums.get(maxIndex).get(0)};
        int index[]=new int[nums.size()];
        int left=nums.get(minIndex).get(0),right=nums.get(maxIndex).get(0);
        index[minIndex]++;
        while(true) {
        	minIndex=0;
        	maxIndex=0;
        	for(int i=1;i<nums.size();++i) {
        		//找出这一趟的最大元素
        		if(nums.get(i).get(index[i])<nums.get(minIndex).get(index[minIndex]))
        			minIndex=i;
        		if(nums.get(i).get(index[i])>nums.get(maxIndex).get(index[maxIndex]))
        			maxIndex=i;
        	}
        	int temp=nums.get(maxIndex).get(index[maxIndex])-nums.get(minIndex).get(index[minIndex]);
        	if(temp<res){
        		res=temp;
        		left=nums.get(minIndex).get(index[minIndex]);
        		right=nums.get(maxIndex).get(index[maxIndex]);
        	}
        	if(index[minIndex]==nums.get(minIndex).size()-1) {//已经到末尾了
        		return new int[] {left,right};
        	}
        	++index[minIndex];
        }
    }

}
